package maxPathSum

import "math"

type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

/*
被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
*/
func maxPathSum(root *TreeNode) int {
	var ans int = math.MinInt
	var maxGain func(*TreeNode) int
	maxGain = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		// 找左边子树的最大值
		leftMax := max(0, maxGain(node.left))
		// 找右边子树的最大值
		rightMax := max(0, maxGain(node.right))
		// 当前节点的所有路径最大值
		ans = max(ans, node.val+leftMax+rightMax)
		// 因为子节点最多只能出现一次，所以返回最大值
		return max(leftMax, rightMax) + node.val
	}
	maxGain(root)
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
